package top.byfree.sort;


import java.util.Arrays;

// 归并排序
public class MergeSort {

    public static void main(String[] args) {
        int[] arr = new int[8000000];
        for (int i = 0; i < 8000000; i++) {
            arr[i] = (int) (Math.random() * 80000000);
        }
        long l = System.currentTimeMillis();
        mergeSort(arr, 0, arr.length - 1);
        long l2 = System.currentTimeMillis();
//        System.out.println(Arrays.toString(arr));
        System.out.println(l2 - l);
    }


    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) { // 当待归并排序数组个数大于一时
            int mid = left + ((right - left) >> 1);
            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);

            merge(arr, left, mid, right);

        }
    }

    public static void merge(int[] arr, int left, int mid, int right) {
        int[] temp = new int[right - left + 1];
        int i = left;
        int j = mid + 1;
        int n = 0;

        while (i <= mid && j <= right) {
            temp[n++] = arr[i] < arr[j] ? arr[i++] : arr[j++];
        }

        while (i <= mid) {
            temp[n++] = arr[i++];
        }
        while (j <= right) {
            temp[n++] = arr[j++];
        }

        for (int k = 0; k < temp.length; k++) {
            arr[left + k] = temp[k];
        }

    }
}
